Day-28 Breadth-First Search(BFS), 廣度優先搜尋

2021 iThome 鐵人賽

DAY 28

自我挑戰組

從0開始啃Introduction of algorithms心得與記錄系列第 28 篇

13th鐵人賽自學筆記 algorithm

吳他，惟手熟爾

2021-10-09 23:40:59

4061 瀏覽

分享至

BFS簡介

BFS是用來遍歷一張圖的最簡單演算法，也是很多在圖論演算法的原型，許多演算法都是基於BFS，像是Prim最小生成樹，Dijkstra演算法等等。

給定一張圖 $G=(V,E)$ ，和一個節點s，BFS可以走訪s能夠到達的所有節點v，並且能夠紀錄s到各個節點的最少邊數，也就是最短距離，同時會產生出一棵BST Tree。這個數會以s作為樹的根結點，並且包含s能夠到達的所有節點v。BST可以用在有向圖，也可以用在無向圖中。

為了方面演示這個演算法，我們將結點以三個顏色做為表示，白色，灰色，黑色做為表示。所有節點在一開始的時候都標記為白色，在BST持續進行的過程，這些節點會變成灰色或是黑色。在遍歷的過程中，第一次遇到的節點就稱為該節點被發現，並且同時節點的顏色發生改變，黑色和灰色皆為已經被發現的節點。

白色表示還沒被其他節點發現的節點，灰色表示被其他節點發現的節點，且被推入Queue中，黑色表示被其他節點發現得節點，且已經被Pop出Queue。

下面為BFS的虛擬碼，假設給定圖 $G=(V,E)$ ，以鄰接矩陣表示，每一個節點作為物件表示，節點的顏色儲存在 $u.color$ 中， $u.\pi$ 儲存前驅節點，如果不存在節點，則表示為NULL， $u.d$ 紀錄s到u的距離。這個演算法還需要一個Queue來儲存灰色的節點。

BFS(G, s)
for each vertex u ∈ G.V - {s}
  u.color = WHITE
  u.d = ∞
  u.π = NULL
s.color = GRAY
s.d = 0
s.π = NULL
Q = ∅
ENQUEUE(Q, s)
while Q != ∅
u = DEQUEUE(Q)
for each v ∈ G.Adj[u]
  if v.color == WHITE
     v.color = GRAY
     v.d = u.d + 1
     v.π = u
     ENQUEUE(Q, v)
u.color = BLACK

(a)一開始從s節點開始，s節點被發現，標記為灰色，同時推入Queue中。
(b)將s彈出Queue，彈出的節點可以看做是目前所在節點，並將s標記為黑色，接著w, r被發現，標記成灰色，同時推入Queue中。1表示s一步就能到達的節點，儲存到v.d中。
(c)將w彈出Queue，並將w標記成黑色，可以將黑色視為目前所在的節點，接著，t和x被發現，標記成灰色，同時推入Queue。2表示s走兩步可以到的節點，步數儲存到v.d中。
(d)將r彈出Queue，並將r標記成黑色，r所在的地方發現到節點v，標記成灰色，並推入Queue，v是s兩步可以走到的節點，步數儲存到v.d中。
(e)將t彈出Queue，並將t標記成黑色，t所在的地方發現到節點u，標記成灰色，並推入Queue，u是s走三步可以走到的節點，步數儲存到v.d中。
(f)將x彈出Queue，並將x標記成黑色，x所在的地方發現到節點y，標記成灰色，並推入Queue，y是s走三步可以走到的節點，步數儲存到v.d中。
(g)將v彈出Queue，並將v標記成黑色，v所在的地方發現不到任何節點。
(h)將u彈出Queue，並將u標記成黑色，u所在的地方發現到y，但y已經在Queue中，故沒有新的節點被推入Queue。
(i)將y彈出Queue，並將y標記成黑色，y所在的地方發現不到任何節點。

在BFS中，一開始構建出的BFS Tree只會有一個根結點s，在遍歷過程中看到u節點的鄰接串列時，每當發現到一個白色節點v，就將結點v和 $(u,v)$ 邊加入到樹中。BFS Tree中，稱u節點是v節點的前驅點或是父節點。

在虛擬碼1到4行中，我們先將s節點從G.V集合中移出，並遍歷除了s的所有節點，都將他標記成白色，並將每一個節點的u.d標記成無限，無限的概念就是走不到的意思，引申為還沒走到的節點，並將每一個父節點標記成NULL。

在第5行將s標記成灰色，因為在BST最一開始時，我們便發現到s了，並且只有s是沒有被標記成白色的，第6行和第7行初始化s。第8,9行初始化Queue，Queue的初始狀態下，裡面只有s。

第10行到18行while迴圈一直執行到沒有灰色節點為止，在第一次迭代，只有s節點是灰色的，Queue中也是只有s節點，直到第11行Pop出來。

第12行到17行for迴圈對u節點的鄰接串列中每一個節點v進行探測，如果v為白色，表示還沒被發現，使用第14行到17行來發現節點，將剛剛白色的v節點塗上灰色，並將v.d = u.d + 1，改變距離，並將u當作是v的父節點，然後插入到Queue的尾端。

在第18行，檢查u的鄰接串列中所有節點後，將u節點標記成黑色。

以樹的形式來看BFS，就可以發現到廣度優先的特性了，我們可以觀察到我們是一層接著一層的去遍歷整棵樹，而這個特性可以給予我們到某一個節點的最短路徑，BFS好處在於可以告訴我們哪一些節點是s抵達不了的。

效率

從上面的例子觀察到，每一個節點最多就是出隊和入隊各一次，而Queue的入隊和出隊操作皆為 $O(1)$ ，總共在集合G.V中有|V|個節點，因此時間複雜度為 $O(V)$ 。BFS只有在節點出隊的時候才會對節點對應到的鄰接串列進行遍歷，而無論是有向圖，還是無向圖，他們的鄰接串列的長度皆為 $\Theta(E)$ ，而整體BFS所需要的時間複雜度為 $O(V) + O(E) = O(V + E)$ ，而這是一個線性函數。